﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace LowLevelGraphics.Dijkstra
{
    /// <summary>
    /// Examples
    /// 
    /// 
    ///Dictionary<string, Node> _dictNodes =
    ///                new Dictionary<string, Node>();
    ///    _dictNodes.Add("A", new Node("A"));
    ///    _dictNodes.Add("B", new Node("B"));
    ///    _dictNodes.Add("C", new Node("C"));
    ///    _dictNodes.Add("D", new Node("D"));
    ///    _dictNodes.Add("E", new Node("E"));
    ///    _dictNodes.Add("F", new Node("F"));

    ///    List<Node> _nodes = new List<Node>();
    ///    foreach (Node n in _dictNodes.Values)
    ///    {
    ///        _nodes.Add(n);
    ///    }

    ///    List<Edge> _edges = new List<Edge>();
    ///    _edges.Add(new Edge(_dictNodes["A"], _dictNodes["B"], 7));
    ///    _edges.Add(new Edge(_dictNodes["A"], _dictNodes["C"], 14));
    ///    _edges.Add(new Edge(_dictNodes["A"], _dictNodes["D"], 9));

    ///    _edges.Add(new Edge(_dictNodes["B"], _dictNodes["A"], 7));
    ///    _edges.Add(new Edge(_dictNodes["B"], _dictNodes["D"], 10));
    ///    _edges.Add(new Edge(_dictNodes["B"], _dictNodes["E"], 15));

    ///    _edges.Add(new Edge(_dictNodes["C"], _dictNodes["A"], 14));
    ///    _edges.Add(new Edge(_dictNodes["C"], _dictNodes["D"], 2));
    ///    _edges.Add(new Edge(_dictNodes["C"], _dictNodes["F"], 9));

    ///    _edges.Add(new Edge(_dictNodes["D"], _dictNodes["C"], 2));
    ///    _edges.Add(new Edge(_dictNodes["D"], _dictNodes["A"], 9));
    ///    _edges.Add(new Edge(_dictNodes["D"], _dictNodes["B"], 10));
    ///    _edges.Add(new Edge(_dictNodes["D"], _dictNodes["E"], 11));

    ///    _edges.Add(new Edge(_dictNodes["E"], _dictNodes["B"], 15));
    ///    _edges.Add(new Edge(_dictNodes["E"], _dictNodes["D"], 11));
    ///    _edges.Add(new Edge(_dictNodes["E"], _dictNodes["F"], 6));

    ///    _edges.Add(new Edge(_dictNodes["F"], _dictNodes["C"], 9));
    ///    _edges.Add(new Edge(_dictNodes["F"], _dictNodes["E"], 6));

    ///    /// Neues Objekt der Klasse Dijkstra erstellen
    ///    Dijkstra d = new Dijkstra(_edges, _nodes);

    ///    /// Startknoten festlegen und Distanzen berechnen
    ///    d.calculateDistance(_dictNodes["A"]);

    ///    /// Pfad zu einem bestimmten Knoten ausgeben
    ///    List<Node> path = d.getPathTo(_dictNodes["F"]);

    ///    if (path.Count > 0)
    ///    {
    ///        foreach (Node n in path)
    ///        {
    ///            Console.Write(n.Name + " ");
    ///        }
    ///        Console.WriteLine("");
    ///    }

    ///    Console.WriteLine("Bitte eine Taste drücken");
    ///    Console.ReadKey();
    ///} 
    /// </summary>
    public class Dijkstra
    {
        private List<Node> _nodes;
        private List<Edge> _edges;
        private List<Node> _basis;
        private Dictionary<string, double> _dist;
        private Dictionary<string, Node> _previous;

        /// <summary>
        /// Konstruktor
        /// </summary>
        /// <param name="edges">Liste aller Kanten</param>
        /// <param name="nodes">Liste aller Knoten</param>
        public Dijkstra(List<Edge> edges, List<Node> nodes)
        {
            _edges = edges;
            _nodes = nodes;
            _basis = new List<Node>();
            _dist = new Dictionary<string, double>();
            _previous = new Dictionary<string, Node>();

            // Knoten aufnehmen
            foreach (Node n in _nodes)
            {
                _previous.Add(n.Name, null);
                _basis.Add(n);
                _dist.Add(n.Name, double.MaxValue);
            }
        }

        /// <summary>
        /// Berechnet die kürzesten Wege vom start
        /// Knoten zu allen anderen Knoten
        /// </summary>
        /// <param name="start">Startknoten</param>
        public void CalculateDistance(Node start)
        {
            _dist[start.Name] = 0;

            while (_basis.Count > 0)
            {
                Node u = GetNodeWithSmallestDistance();
                if (u == null)
                {
                    _basis.Clear();
                }
                else
                {
                    foreach (Node v in GetNeighbors(u))
                    {
                        double alt = _dist[u.Name] +
                                GetDistanceBetween(u, v);
                        if (alt < _dist[v.Name])
                        {
                            _dist[v.Name] = alt;
                            _previous[v.Name] = u;
                        }
                    }
                    _basis.Remove(u);
                }
            }
        }

        /// <summary>
        /// Liefert den Pfad zum Knoten d
        /// </summary>
        /// <param name="d">Zielknote<n/param>
        /// <returns></returns>
        public List<Node> getPathTo(Node d)
        {
            List<Node> path = new List<Node>();

            path.Insert(0, d);

            while (_previous[d.Name] != null)
            {
                d = _previous[d.Name];
                path.Insert(0, d);
            }

            return path;
        }

        /// <summary>
        /// Liefert den Knoten mit der kürzesten Distanz
        /// </summary>
        /// <returns></returns>
        public Node GetNodeWithSmallestDistance()
        {
            double distance = double.MaxValue;
            Node smallest = null;

            foreach (Node n in _basis)
            {
                if (_dist[n.Name] < distance)
                {
                    distance = _dist[n.Name];
                    smallest = n;
                }
            }

            return smallest;
        }

        /// <summary>
        /// Liefert alle Nachbarn von n die noch in der Basis sind
        /// </summary>
        /// <param name="n">Knoten</param>
        /// <returns></returns>
        public List<Node> GetNeighbors(Node n)
        {
            List<Node> neighbors = new List<Node>();

            foreach (Edge e in _edges)
            {
                if (e.Origin.Equals(n) && _basis.Contains(n))
                {
                    neighbors.Add(e.Destination);
                }
            }

            return neighbors;
        }

        /// <summary>
        /// Liefert die Distanz zwischen zwei Knoten
        /// </summary>
        /// <param name="o">Startknoten</param>
        /// <param name="d">Endknoten</param>
        /// <returns></returns>
        public double GetDistanceBetween(Node o, Node d)
        {
            foreach (Edge e in _edges)
            {
                if (e.Origin.Equals(o) && e.Destination.Equals(d))
                {
                    return e.Distance;
                }
            }

            return 0;
        }
    }
}
